#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a self-adjusting <see cref="BinarySearchTree&lt;T&gt;"/> with the 
    /// additional property that recently accessed elements are quick to access again.
    /// </summary>
    /// <typeparam name="T">The type of the data in the collection.</typeparam>
    [Serializable]
    public class SplayTree<T> : BinarySearchTree<T>
    {
        /// <summary>
        /// Gets the maximum value in the tree.
        /// </summary>
        /// <value>The maximum value in the tree.</value>
        public override T Max
        {
            get
            {
                T max = base.Max;
                Splay(max);
                return max;
            }
        }

        /// <summary>
        /// Gets the minimum value in the tree.
        /// </summary>
        /// <value>The minimum value tree.</value>
        public override T Min
        {
            get
            {
                T min = base.Min;
                Splay(min);
                return min;
            }
        }

        /// <summary>
        ///   Adds an item to the <see cref="SplayTree&lt;T&gt;"/>.
        /// </summary>
        /// <param name = "value">The object to add to the <see cref="SplayTree&lt;T&gt;"/>.
        /// </param>
        public override void Add(T value)
        {
            if (_Root == null)
            {
                _Root = new BinaryTreeNode<T>(value);
                Count++;
                return;
            }
            Splay(value);
            int result = Comparer.Compare(value, _Root.Value);
            if (result == 0)
                return;
            var newNode = new BinaryTreeNode<T>(value);
            if (result < 0)
            {
                newNode.Left = _Root.Left;
                newNode.Right = _Root;
                _Root.Left = null;
            }
            else
            {
                newNode.Right = _Root.Right;
                newNode.Left = _Root;
                _Root.Right = null;
            }
            _Root = newNode;
            Count++;
        }

        /// <summary>
        ///   Removes the first occurrence of a specific object from the <see cref="SplayTree&lt;T&gt;"/>.
        /// </summary>
        /// <param name="item">The object to remove from the <see cref="SplayTree&lt;T&gt;"/>.
        /// </param>
        /// <returns>
        ///   <c>true</c> if <paramref name="item" /> was successfully removed from the <see cref="SplayTree&lt;T&gt;"/>;
        /// 		otherwise, <c>false</c>. This method also returns <c>false</c> if <paramref name="item" /> is not found in the original
        /// 		<see cref="SplayTree&lt;T&gt;"/>.
        /// </returns>
        public override bool Remove(T item)
        {
            if (_Root == null)
            {
                return false;
            }
            Splay(item);
            if (Comparer.Compare(item, _Root.Value) == 0)
            {
                if (_Root.Left == null)
                {
                    _Root = _Root.Right;
                }
                else
                {
                    BinaryTreeNode<T> temp = _Root.Right;
                    _Root = _Root.Left;
                    Splay(item);
                    _Root.Right = temp;
                }
                Count--;
                return true;
            }

            return false;
        }

        /// <summary>
        /// Finds the specified value from <see cref="SplayTree&lt;T&gt;"/>.
        /// </summary>
        /// <param name="value">The value to find from the <see cref="SplayTree&lt;T&gt;"/>.</param>
        /// <returns>
        /// A <see cref="BinaryTreeNode&lt;T&gt;"/> object is search is successful; otherwise, <c>null</c>.
        /// </returns>
        public override BinaryTreeNode<T> Find(T value)
        {
            BinaryTreeNode<T> node = base.Find(value);
            if (node != null)
            {
                Splay(node.Value);
            }
            return node;
        }

        /// <summary>
        ///   Determines whether the <see cref="SplayTree&lt;T&gt;"/> contains a specific value.
        /// </summary>
        /// <returns>
        ///   <c>true</c> if <paramref name = "item" /> is found in the <see cref="SplayTree&lt;T&gt;"/>; otherwise, <c>false</c>.
        /// </returns>
        /// <param name = "item">The object to locate in the <see cref="SplayTree&lt;T&gt;"/>.
        /// </param>
        public override bool Contains(T item)
        {
            bool result = base.Contains(item);
            if (result)
            {
                Splay(item);
            }
            return result;
        }

        private void Splay(T value)
        {
            var header = new BinaryTreeNode<T>();
            BinaryTreeNode<T> left = header;
            BinaryTreeNode<T> right = header;
            BinaryTreeNode<T> temp = _Root;

            while (true)
            {
                BinaryTreeNode<T> rotateTree;
                if (Comparer.Compare(value, temp.Value) < 0)
                {
                    if (temp.Left == null)
                    {
                        break;
                    }
                    if (Comparer.Compare(value, temp.Left.Value) < 0)
                    {
                        rotateTree = temp.Left;
                        temp.Left = rotateTree.Right;
                        rotateTree.Right = temp;
                        temp = rotateTree;
                        if (temp.Left == null)
                        {
                            break;
                        }
                    }
                    right.Left = temp;
                    right = temp;
                    temp = temp.Left;
                }
                else if (Comparer.Compare(value, temp.Value) > 0)
                {
                    if (temp.Right == null)
                    {
                        break;
                    }
                    if (Comparer.Compare(value, temp.Right.Value) > 0)
                    {
                        rotateTree = temp.Right;
                        temp.Right = rotateTree.Left;
                        rotateTree.Left = temp;
                        temp = rotateTree;
                        if (temp.Right == null)
                        {
                            break;
                        }
                    }
                    left.Right = temp;
                    left = temp;
                    temp = temp.Right;
                }
                else
                {
                    break;
                }
            }
            left.Right = temp.Left;
            right.Left = temp.Right;
            temp.Left = header.Right;
            temp.Right = header.Left;
            _Root = temp;
        }
    }
}